<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
            滑动窗口--固定滑动窗口
            时间复杂度：O(n)，并不是两个循环就是O(n)，每个元素至多进去一次，出来一次，就是O(n * 2) 也就是O(n)
            空间复杂度：O(1)
        */
      var minWindow = function (s, t) {
        const need = new Map();
        const window = new Map();

        // 初始化 need 字典
        for (const c of t) {
          need.set(c, (need.get(c) || 0) + 1);
        }

        // 窗口左指针和右指针
        let left = 0,
          right = 0;
        // 当前窗口中满足t中字符的种类数
        let valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        let start = 0,
          len = Infinity;
        while (right < s.length) {
          // 右移窗口：如果右移放在这里，区间就是左开右开，下面更新len = right - left否则就是 len = right - left + 1
          const c = s[right];
          right++;
          // 更新window
          if (need.has(c)) {
            window.set(c, (window.get(c) || 0) + 1);
            if (window.get(c) === need.get(c)) {
              valid++;
            }
          }

          // 开始缩小窗口：当valid和need的size一致，表示匹配到要求的字符串了
          while (valid === need.size) {
            // 如果当前窗口比之前记录的窗口更小
            if (right - left + 1 < len) {
              start = left; // 更新最小覆盖子串的起始位置
              len = right - left; // 更新最小覆盖子串的长度
            }
            // 左移窗口
            // d是将移出窗口的字符，易错：先获取left，再改为left++
            const d = s[left];
            left++;
            if (need.has(d)) {
              // 如果need窗口里面有d，并且window和need的值相同，则更新valid的值
              if (window.get(d) === need.get(d)) {
                valid--;
              }
              // window的则都要更新
              window.set(d, window.get(d) - 1);
            }
          }
          // 右移窗口，如果右移放在最后，就是左闭右闭，len = right - left + 1
          //   right++;
        }
        // 返回最小覆盖子串
        return len === Infinity ? "" : s.substr(start, len);
      };

      // console.log(findAnagrams("baa", "aa"));
      console.log(minWindow("ADOBECODEBANC", "ABC"));
    </script>
  </body>
</html>
